package com.le.ji.剑指Offer;

import com.sun.source.tree.Tree;
import org.apache.poi.xwpf.usermodel.IBody;

import javax.xml.stream.FactoryConfigurationError;
import java.util.*;


//Definition for singly-linked list.

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {
    }

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    public int[] sortArrayByParity2(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (compareByParity(nums[j], nums[j + 1]) == -1) {
                    int tep;
                    tep = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = tep;
                }
            }
        }
        return nums;
    }

    //
    public int compareByParity(int x1, int x2) {
        if ((x1 % 2 == 0 && x2 % 2 == 0) || (x1 % 2 == 1 && x2 % 2 == 1)) return 0;
        if (x1 % 2 == 0) return 1;
        else return -1;
    }

    public int findRepeatNumber(int[] nums) {
        int[] lis = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            lis[i] = 0;
        }
        for (int number : nums) {
            lis[number] = lis[number] + 1;
            if (lis[number] >= 2) {
                return number;
            }
            ;
        }
        return 0;
    }

    public int[] runningSum(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            nums[i] = nums[i] + nums[i - 1];
        }
        return nums;
    }

    public int pivotIndex(int[] nums) {
        int length = nums.length;
        int[] num1 = nums.clone();
        int[] num2 = new int[length];
        int j = 0;
        for (int i = length - 1; i >= 0; i--, j++) {
            num2[j] = num1[i];
        }
        for (int i = 1; i < nums.length; i++) {
            nums[i] = nums[i] + nums[i - 1];
        }
        for (int i = 1; i < nums.length; i++) {
            num2[i] = num2[i] + num2[i - 1];
        }
        for (int i = 0; i < length; i++) {
            if (num1[i] == num2[length - 3 - i]) return i;
        }
        return -1;
    }

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(-1);
        ListNode prev = new ListNode();
        prev = dummy;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                prev.next = list1;
                list1 = list1.next;
            } else {
                prev.next = list2;
                list2 = list2.next;
            }
            prev = prev.next;
        }
        prev.next = list2 == null ? list1 : list2;
        return dummy.next;
    }

    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        ListNode next;
        while (curr != null) {
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

    public ListNode middleNode(ListNode head) {
        ListNode curr = head;
        int length = 0;
        while (curr != null) {
            length++;
            curr = curr.next;
        }
        curr = head;
        length = length / 2;
        while (length != 0) {
            curr = curr.next;
            length--;
        }
        return curr;
    }

    public ListNode detectCycle(ListNode head) {
        ListNode[] listNodes = new ListNode[10000];
        if (head == null) {
            return null;
        }
        ListNode curr = head.next;
        listNodes[0] = head;
        int i = 1;
        int length = 1;
        while (curr != null) {
            length = i;
            while (length != 0) {
                if (curr == listNodes[length - 1]) {
                    return curr;
                } else {
                    length--;
                }
            }
            listNodes[i] = curr;
            curr = listNodes[i].next;
            i++;
        }
        return null;
    }

    public int maxProfit(int[] prices) {
        if (prices.length == 0) return 0;
        int maxProfit = 0;
        int minValue = maxValueOfArrary(prices);
        for (int number :
                prices) {
            if (number < minValue) minValue = number;
            else {
                if (number - minValue > maxProfit) maxProfit = number - minValue;
            }
        }
        return maxProfit;
    }

    public static int maxValueOfArrary(int[] nums) {
        int maxValue = nums[0];
        for (int number : nums) {
            if (number > maxValue) maxValue = number;
        }
        return maxValue;
    }

    public static int minValueOfArrary(int[] nums) {
        int minValue = nums[0];
        for (int number : nums) {
            if (number < minValue) minValue = number;
        }
        return minValue;
    }

    public List<Integer> preorder(Node root) {
        List<Integer> ans = new ArrayList<>();
        preOrder(root, ans);
        return ans;
    }

    public void preOrder(Node root, List<Integer> ans) {
        if (root == null) {
            return;
        }
        ans.add(root.val);
        List<Node> nodes = root.children;
        for (Node node : nodes) {
            preOrder(node, ans);
        }
    }

    public Map<Integer, List<Integer>> valueDeepMap = new HashMap<>();

    public void preOrder2(TreeNode root, int deep) {
        if (root == null) {
            return;
        }
        System.out.println(root.val + " " + Integer.toString(deep));
        List<Integer> list;
        if (valueDeepMap.get(deep) == null) {
            list = new ArrayList<>();
        } else {
            list = valueDeepMap.get(deep);
        }
        list.add(root.val);
        valueDeepMap.put(deep, list);
        preOrder2(root.left, deep + 1);
        preOrder2(root.right, deep + 1);
    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        preOrder2(root, 1);
        Set<Integer> keySet = valueDeepMap.keySet();
        for (Integer key :
                keySet) {
            ans.add(valueDeepMap.get(key));
        }
        return ans;
    }

    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int mid;
        while (left <= right) {
            mid = (left + right) / 2;
            if (nums[mid] == target) return mid;
            else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }


    public boolean mark = true;

    public void preOrderAndBST(TreeNode root, List<Boolean> marks) {
        if (root == null) return;
        mark = isValid(root);
        marks.add(mark);
        if (mark) {
            preOrderAndBST(root.left, marks);
            preOrderAndBST(root.right, marks);
        }
    }

    public boolean isValid(TreeNode root) {
        if (root.left != null && !leftIsValid(root)) return false;
        return root.right == null || rightIsValid(root);
    }

    public void ValList(TreeNode root, List<Integer> lis) {
        if (root == null) return;
        lis.add(root.val);
        ValList(root.left, lis);
        ValList(root.right, lis);
    }

    public boolean leftIsValid(TreeNode root) {
        List<Integer> leftVal = new ArrayList<>();
        ValList(root.left, leftVal);
        if (root.val == 26) System.out.println(leftVal);
        for (int item : leftVal) {
            if (item >= root.val) return false;
        }
        return true;
    }

    public boolean rightIsValid(TreeNode root) {
        List<Integer> rightVal = new ArrayList<>();
        ValList(root.right, rightVal);
        for (int item : rightVal) {
            if (item <= root.val) return false;
        }
        return true;
    }

    public boolean isValidBST(TreeNode root) {
        List<Boolean> marks = new ArrayList<>();
        preOrderAndBST(root, marks);
        for (boolean mark :
                marks) {
            if (!mark) return false;
        }
        return true;
    }


    public void searchFromBST(TreeNode root, TreeNode targetNode, List<TreeNode> ans) {
        if (root == null) return;
        if (targetNode.val == root.val) {
            ans.add(root);
        } else {
            if (targetNode.val < root.val) {
                ans.add(root);
                searchFromBST(root.left, targetNode, ans);
            } else {
                ans.add(root);
                searchFromBST(root.right, targetNode, ans);
            }
        }
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> pList = new ArrayList<>();
        List<TreeNode> qList = new ArrayList<>();
        searchFromBST(root, p, pList);
        searchFromBST(root, q, qList);
        for (int i = pList.size() - 1; i >= 0; i--) {
            TreeNode currentPNode = pList.get(i);
            for (int j = qList.size() - 1; j >= 0; j--) {
                TreeNode currentQNode = qList.get(j);
                if (currentPNode == currentQNode) {
                    return currentQNode;
                }
            }
        }
        return root;
    }


    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        int rowColor = image[sr][sc];
        int[][] visited = new int[image.length][image[0].length];
        DFS(image, visited, sr, sc, rowColor, color);
        return image;
    }

    public void DFS(int[][] image, int[][] visited, int x, int y, int rowColor, int newColor) {
        visited[x][y] = 1;  //标记已走过
        image[x][y] = image[x][y] == rowColor ? newColor : image[x][y];
        if (x - 1 >= 0 && visited[x - 1][y] != 1 && image[x - 1][y] == rowColor)
            DFS(image, visited, x - 1, y, rowColor, newColor); //向上填充
        if (x + 1 <= image.length - 1 && visited[x + 1][y] != 1 && image[x + 1][y] == rowColor)
            DFS(image, visited, x + 1, y, rowColor, newColor); //向下填充
        if (y - 1 >= 0 && visited[x][y - 1] != 1 && image[x][y - 1] == rowColor)
            DFS(image, visited, x, y - 1, rowColor, newColor); //向左填充
        if (y + 1 <= image[0].length - 1 && visited[x][y + 1] != 1 && image[x][y + 1] == rowColor)
            DFS(image, visited, x, y + 1, rowColor, newColor); //向右填充
    }


    public int numIslands(char[][] grid) {
        int[][] visited = new int[grid.length][grid[0].length];
        int ans = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1' && visited[i][j] != 1) {
                    DFS(grid, visited, i, j);
                    ans++;
                }
            }
        }
        return ans;
    }

    public void DFS(char[][] image, int[][] visited, int x, int y) {
        visited[x][y] = 1;  //标记已走过
        if (x - 1 >= 0 && visited[x - 1][y] != 1 && image[x - 1][y] == '1')
            DFS(image, visited, x - 1, y); //向上填充
        if (x + 1 <= image.length - 1 && visited[x + 1][y] != 1 && image[x + 1][y] == '1')
            DFS(image, visited, x + 1, y); //向下填充
        if (y - 1 >= 0 && visited[x][y - 1] != 1 && image[x][y - 1] == '1')
            DFS(image, visited, x, y - 1); //向左填充
        if (y + 1 <= image[0].length - 1 && visited[x][y + 1] != 1 && image[x][y + 1] == '1')
            DFS(image, visited, x, y + 1); //向右填充
    }


    public int minCostClimbingStairs(int[] cost) {
        int[] dp = new int[cost.length + 1];  //dp[i]表示达到第i级阶梯时的最小花费
        dp[0] = dp[1] = 0;
        for (int i = 2; i <= cost.length; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[dp.length - 1];
    }


    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        // 第一行和第一列的可能路径数都是只有1条（边界）
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int i = 0; i < n; i++) {
            dp[0][i] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; //[i][j]位置上的路径为 其左边一格和上方一格 的路径和(棋子只能向右或向下移动)
            }
        }
        return dp[n - 1][m - 1];
    }

    public List<Integer> findAnagrams(String s, String p) {
        int pLength = p.length();
        char[] chars = p.toCharArray();
        List<Integer> ans = new ArrayList<>();
        int counts;

        for (int i = 0; i <= s.length() - pLength; i++) {
            Map<Character, Integer> map = new HashMap<>();
            for (int m = 0; m < pLength; m++) {
                if (mapContainChar(chars[m], map)) {
                    counts = map.get(chars[m]);
                    counts++;
                    map.put(chars[m], counts);
                } else {
                    map.put(chars[m], 1);
                }
            }
            char[] currentS = s.substring(i, i + pLength).toCharArray();
            for (char current : currentS) {
                if (charIsContainInString(current, p)) {
                    int count = map.get(current);
                    map.put(current, count - 1);
                }
            }
            List<Integer> valueSet = new ArrayList<>();
            for (Character key : map.keySet()) {
                valueSet.add(map.get(key));
            }
            int mark = 0;
            for (int count : valueSet) {
                if (count != 0) break;
                else mark++;
            }
            if (mark == valueSet.size()) ans.add(i);
        }
        return ans;
    }

    public boolean mapContainChar(char x, Map<Character, Integer> map) {
        Set<Character> keySet = map.keySet();
        for (Character item : keySet) {
            if (item == x) return true;
        }
        return false;
    }

    public boolean charIsContainInString(char x, String s) {
        char[] chars = s.toCharArray();
        for (char item :
                chars) {
            if (item == x) return true;
        }
        return false;
    }

    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target)
                    return new int[]{i, j};
            }
        }
        return new int[]{0, 0};
    }


    public boolean backspaceCompare(String s, String t) {
        List<Character> stack = new ArrayList<>();
        List<Character> stack2 = new ArrayList<>();
        char[] charsOfS = s.toCharArray();
        char[] charsOft = t.toCharArray();
        fun(stack, charsOfS);
        fun(stack2, charsOft);
        return stack.equals(stack2);
    }

    public void fun(List<Character> stack2, char[] charsOft) {
        for (char x : charsOft) {
            if (!stack2.isEmpty() && x == '#') {
                stack2.remove(stack2.size() - 1);
            } else if (stack2.isEmpty() && x == '#') {
                System.out.println("栈为空时执行出栈");
            } else {
                stack2.add(x);
            }
        }
    }

    public String decodeString(String s) {
        StringBuffer ans = new StringBuffer();
        Stack<Integer> stackOfMuti = new Stack<>();
        Stack<StringBuffer> stackOfAns = new Stack<>();
        int multi = 0;
        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) multi = multi * 10 + c - '0';
            else if (c == '[') {
                stackOfAns.add(ans);
                stackOfMuti.add(multi);
                ans = new StringBuffer();
                multi = 0;
            } else if (Character.isAlphabetic(c)) {
                ans.append(c);
            } else {
                StringBuffer ansTmp = stackOfAns.pop();
                int tmp = stackOfMuti.pop();
                ansTmp.append(String.valueOf(ans).repeat(Math.max(0, tmp)));
                ans = ansTmp;
            }
        }
        return ans.toString();
    }

    public int lastStoneWeight(int[] stones) {
        Arrays.sort(stones);
        List<Integer> lis = arraysToList(stones);
        while (lis.size() > 1) {
            int size = lis.size();
            if (Objects.equals(lis.get(size - 1), lis.get(size - 2))) {
                lis.remove(size-1);
                lis.remove(size-2);
            }
            else if (!Objects.equals(lis.get(size - 1), lis.get(size - 2))) {
                int num1 = lis.get(size-1);
                int num2 = lis.get(size-2);
                lis.remove(size-1);
                lis.remove(size-2);
                insertSortedList(lis, num1 - num2);
            }
        }
        if (lis.size() == 0) return 0;
        return lis.get(0);
    }


    public void insertSortedList(List<Integer> lis, int number) {
        int length = lis.size();
        for (int i = 0; i < length; i++) {
            if (number < lis.get(i)) {
                lis.add(i, number);
                break;
            }
            if (i == length-1 && number >= lis.get(i)) {
                lis.add(number);
            }
        }
        if (length == 0) lis.add(number);
    }

    public List<Integer> arraysToList(int[] arrays) {
        List<Integer> res = new ArrayList<>();
        for (Integer num : arrays) {
            res.add(num);
        }
        return res;
    }


    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> ans = new ArrayList<>();
        int rows = matrix.length;
        int cols = matrix[0].length;
        int i = 0;
        int j = 0;
        int iStart = 1;
        int jStart = 0;
        int count = rows * cols;
        boolean left = false;
        boolean right = true;
        boolean up = false;
        boolean down = false;
        while (count > 0) {
            ans.add(matrix[i][j]);
//            System.out.println(matrix[i][j]);
            if (j == cols-1 && right) {
                right = false;
                down = true;
                cols--;
            } else if (i == rows-1 && down) {
                down = false;
                left = true;
                rows--;
            } else if (j == jStart && left) {
                left = false;
                up = true;
                jStart++;
            } else if (i == iStart  && up) {
                up = false;
                right = true;
                iStart++;
            }
//            System.out.println(down);
            if (right) {
                j++;
            } else if (down) {
                i++;
            } else if (left) {
                j--;
            } else if (up) {
                i--;
            }
            count--;
//            System.out.print(i);
//            System.out.print(" ");
//            System.out.print(j);
//            System.out.println();
        }

        return ans;
    }


    public List<Integer> ans = new ArrayList<>();

    public int[] findBall(int[][] grid) {
        for (int i = 0; i < grid[0].length; i++) {
            DfsOfBall(grid, 0, i);
//            System.out.println("——————————————————————————————————————");
        }
        int[] res = new int[ans.size()];
        for (int i = 0; i < ans.size(); i++) {
            res[i] = ans.get(i);
        }
        return res;
    }

    public void DfsOfBall(int[][] grid, int i, int j) {
        int rows = grid.length;
        int cols = grid[0].length;
//        System.out.println(i + " " + j);
        if (i == rows) {
            ans.add(j);
            return;
        }
        if (grid[i][j] == 1) {
            if (j+1 == cols) {
                ans.add(-1);
                return;
            }
            if (grid[i][j+1] == -1) {
                ans.add(-1);
                return;
            } else {
                DfsOfBall(grid, i+1, j+1);
            }
        } else {
            if (j-1 == -1) {
                ans.add(-1);
                return;
            }
            if (grid[i][j-1] == 1) {
                ans.add(-1);
                return;
            } else {
                DfsOfBall(grid, i+1, j-1);
            }
        }
    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode curr = head;
        int length = 0;
        while (curr != null) {
            curr = curr.next;
            length++;
        }
        if (length == 1) return null;
        curr = head;
        length = length - n - 1;
        if (length == -1) {
            return head.next;
        }
        while (length > 0) {
            curr = curr.next;
            length--;
        }
        curr.next = curr.next.next;
        return head;
    }

    public ListNode oddEvenList(ListNode head) {
        ListNode evenList = new ListNode();
        ListNode tail = evenList;
        ListNode p = head;
        if (p == null) return head;
        if (p.next == null) return head;
        if (p.next.next == null) return head;
        while (p != null && p.next != null) {
            if (p.next.next == null) {
                tail.next = p.next;
                tail = tail.next;
                break;
            }
            tail.next = p.next;
            p.next = p.next.next;
            p = p.next;
            tail = tail.next;
        }
        p.next = evenList.next;
        tail.next = null;
        return head;
    }

    public ListNode sortList(ListNode head) {
        ListNode newOrdedLinkList = null;
        ListNode curr = head;
        while (curr != null) {
            newOrdedLinkList = insertDataToSortedLinkList(newOrdedLinkList, new ListNode(curr.val));
            curr = curr.next;
        }
        return newOrdedLinkList;
    }

    public ListNode sortList2(ListNode head) {
        List<Integer> list = new ArrayList<>();
        ListNode curr = head;
        while (curr != null) {
            list.add(curr.val);
            curr = curr.next;
        }
        list.sort((o1, o2) -> o1.compareTo(o2));
        ListNode newOrdedLinkList = new ListNode();
        ListNode tail = newOrdedLinkList;
        for (int x : list) {
            tail.next = new ListNode(x);
            tail = tail.next;
        }
        tail.next = null;
        return newOrdedLinkList.next;
    }

    public ListNode insertDataToSortedLinkList(ListNode head, ListNode node) {
        ListNode curr = head;
        ListNode pre = new ListNode(-1, head);
        if (head == null) {
            return node;
        }
        if (node.val <= head.val) {
            pre.next = node;
            node.next = head;
            return pre.next;
        }
        while (curr != null && curr.val <= node.val) {
            pre = pre.next;
            curr = curr.next;
        }
        pre.next = node;
        if (curr != null) {
            node.next = curr;
        }
        return head;
    }


    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        } else {
            return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
        }
    }

    public int height(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = height(root.left);
        int right = height(root.right);
        if (left == -1 || right == -1 || Math.abs(left - right) > 1) {
            return -1;
        } else {
            return Math.max(left, right) + 1;
        }
    }

    public int ans2;

    public int diameterOfBinaryTree(TreeNode root) {
        ans2 = 1;
        deepth(root);
        return ans2 - 1;
    }

    public int deepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftDeepth = deepth(root.left);
        int rightDeepth = deepth(root.right);
        ans2 = Math.max(ans2, leftDeepth + rightDeepth + 1);
        return Math.max(leftDeepth, rightDeepth) + 1;
    }

    public int pathNumber;

    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return 0;
        }
        AddPath(root, targetSum);
        pathSum(root.left, targetSum);
        pathSum(root.right, targetSum);
        return pathNumber;
    }

    public void AddPath(TreeNode root, int targetSum) {
        if (root == null) {
            return;
        }
        targetSum -= root.val;
        if (targetSum == 0) {
            pathNumber++;
        }
        AddPath(root.left, targetSum);
        AddPath(root.right, targetSum);
    }

    public boolean isExistItem(int[] list, int target) {
        int left = 0;
        int right = list.length - 1;
        int mid;
        while (left <= right) {
            mid = (left + right) / 2;
            if (list[mid] == target) {
                return true;
            } else if (list[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return false;
    }

    public boolean searchMatrix(int[][] matrix, int target) {
        int cols = matrix[0].length;
        for (int[] ints : matrix) {
            if (target >= ints[0] && target <= ints[cols - 1]) {
                return isExistItem(ints, target);
            }
        }
        return false;
    }

    public int search2(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        int length = nums.length;
        int[] newNums = new int[length];
        int pos = 0;
        for (int i = 1; i < length; i++) {
            if (nums[i] < nums[i-1]) {
                pos = i;
            }
            map.put(nums[i], i);
        }
        map.put(nums[0], 0);
        for (int i = 0; i < length; i++) {
            newNums[i] = nums[pos];
            pos++;
            if (pos == length) {
                pos = 0;
            }
        }
//        System.out.println(Arrays.toString(newNums));
        int temp = searchItem(newNums, target);
        if ( temp == -1 ) {
            return -1;
        } else {
            return map.get(newNums[temp]);
        }
    }

    public int searchItem(int[] list, int target) {
        int left = 0;
        int right = list.length - 1;
        int mid;
        while (left <= right) {
            mid = (left + right) / 2;
            if (list[mid] == target) {
                return mid;
            } else if (list[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1; // 表示数组中不存在目标值
    }


    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1};
        System.out.println(solution.search2(nums, 1));
    }
}
